Grokking Algorithm Complexity and Big-O
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Course Overview
Basics of Algorithm Analysis
Introduction to Algorithm Analysis
Measuring Efficiency
Functions and Their Growth Rates
Asymptotic Notations
Overview of Asymptotic Analysis
Big-O Notation (O-notation)
Big-Omega Notation (Ω-notation)
Big-Theta Notation (Θ-notation)
Little-o and Little-omega Notations
Comparing Asymptotic Notations
Time Complexity Analysis
Understanding Time Complexity
Analyzing Control Structures
Analyzing Simple Algorithms
Best, Worst, and Average Cases
Constant Time: O(1)
Linear Time: O(n)
Quadratic Time: O(n²)
Quiz
Space Complexity Analysis
Understanding Space Complexity
Analyzing Space Complexity of Algorithms
Constant Space: O(1)
Linear Space: O(n)
Quadratic Space: O(n²)
Quiz
Analyzing Recursive Algorithms
Introduction to Recursion
Recursion Tree Method
Recurrence Relation Method
Master Theorem Method
Space Complexity Analysis of Recursive Algorithm
Logarithmic Time and Space: O(log n)
Linearithmic Time: O(n log n)
Exponential Time and Space: O(2ⁿ)
Quiz
Array
Linked List
Hash Table and Set
Stack and Queue
Binary Search Tree
Quiz
Sorting Algorithms
Graph Algorithms
Dynamic Programming Algorithms
Coding Interview Problems
Trade-offs in Algorithm Design
Logarithmic Time and Space: O(log n)

Logarithmic Time Complexity and Logarithmic Space Complexity occur in algorithms that repeatedly reduce the problem size by a constant factor (often halving). This type of complexity is common in algorithms that use recursive division, such as finding powers or performing binary searches.

Image

Key Characteristics

In an algorithm with time and space complexity:

  • Time Complexity: The runtime grows logarithmically as the input size increases, due to dividing the problem in each step.

  • Space Complexity: The memory usage grows logarithmically with the input size due to the depth of the recursive call stack.

Code Example

Here’s a recursive example that demonstrates complexity. This function calculates the largest power of two less than or equal to a given number, n, by repeatedly halving n.

Java
Saved to Cloud

. . . .
  • Explanation: This function keeps dividing n by 2 until n becomes 1 or less, adding 1 to the count at each step.

Analyzing the Time Complexity Using Recurrence Relation

To understand the time complexity, let’s set up a recurrence relation for the function:

Step 1: Define the Recurrence Relation

  • Let represent the time complexity of largest_power_of_two for an input of size n.
  • Each time we call largest_power_of_two(n // 2), we halve n, so we can express the time complexity as:

Here:

  • represents the recursive call with input size halved.
  • represents the constant work done in each recursive step (the addition).

Step 2: Solve the Recurrence Relation

  • Let’s expand this recurrence relation step by step to understand the total number of recursive calls.

  • The process continues until the input size is reduced to 1, at which point the function stops. This happens when , which simplifies to:

  • Taking the logarithm of both sides, we get:

  • So, because there are recursive calls before reaching the base case.

Analyzing Space Complexity Using Recurrence Relation

The space complexity also grows logarithmically because each recursive call uses a stack frame, and the maximum number of stack frames corresponds to the depth of recursion.

  1. Define the Space Recurrence Relation:
    • Let represent the space complexity.
    • Each recursive call adds one frame to the call stack, and the stack grows as the input is halved:

  1. Recursive Depth and Space Complexity:
    • Similar to the time complexity, the recursion depth reaches .
    • Therefore, the space complexity is also:
Space Complexity Analysis of Recursive Algorithm
Linearithmic Time: O(n log n)
Mark as Completed

On this page

Key Characteristics

Code Example

Analyzing the Time Complexity Using Recurrence Relation

Analyzing Space Complexity Using Recurrence Relation